package internal.selection;

import java.util.Arrays;

/**
 * @描述：堆排序将是所有的数据先建成一个堆，如大顶堆（最大的数据在堆顶），然后将堆顶数据和序列的最后一个数据交换，然后重新建堆，交换数据，依次下去，就可以排序所有的数据。
 * @适用场合：由于不需要大量的递归或者多维的暂存数组，因此这对于数据量非常巨大的序列是很合适的，比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。
 * @作者：hongxingfan
 * @时间：2014年9月5日 下午5:00:54
 */
public class HeapSort {

    public static void main(String[] args) {
        int[] datas = { 19, 4, 1, 8, 7, 52, 2, 45, 30, 4, 6 };

        heapSort(datas);

        System.out.println(Arrays.toString(datas));
    }

    public static void heapSort(int[] datas) {
        int length = datas.length;
        for (int i = 0; i < length - 1; i++) {
            buildMaxHeap(datas, length - i - 1);
            swap(datas, 0, length - i - 1);
        }
    }

    // 建堆的过程是很复杂的过程需要很好的理解
    public static void buildMaxHeap(int[] datas, int lastIndex) {
        for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
            int k = i;
            while (k * 2 + 1 <= lastIndex) {
                int biggerIndex = 2 * k + 1;
                if (biggerIndex < lastIndex) {
                    if (datas[biggerIndex] < datas[biggerIndex + 1])
                        biggerIndex++;
                }
                if (datas[k] < datas[biggerIndex]) {
                    swap(datas, k, biggerIndex);
                    k = biggerIndex;
                } else {
                    break;
                }
            }
        }
    }

    public static void swap(int[] datas, int i, int j) {
        int tmp = datas[i];
        datas[i] = datas[j];
        datas[j] = tmp;
    }
}